#include <ostream>
#include <iostream>
using namespace std;
#define NULL 0
template <class T>
class Node {
public:
	template<class T>
	friend class LinkList;
	Node();
	Node(const T& data);
	Node(const T& data, Node<T>* head, Node<T>* tail);
	~Node();
private:
	T data;
	Node<T>* head;
	Node<T>* tail;
};

template<typename T>
Node<T>::Node()
{
	data = 0;
	head = tail = NULL;
}
template<typename T>
Node<T>::Node(const T& data)
{
	this->data = data;
	head = tail = NULL;
}
template<typename T>
Node<T>::~Node()
{

}
template<typename T>
Node<T>::Node(const T& data, Node<T>* head, Node<T>* tail)
{
	this->data = data;
	this->head = head;
	this->tail = tail;
}
template <class T>
class LinkList {
public:
	LinkList();
	LinkList(const LinkList<T>& List);
	~LinkList();
	T& get(int theIndex) const;
	int indexOf(const T& theElement) const;
	bool isEmpty();
	int getsize() { return listSize; }
	void erase(int theIndex);
	void insert(int theIndex, const T& theElement);
	void output(std::ostream& out) const;
	void out(std::ostream& out) const;
	void push_back(const T& theElement);
	LinkList<T>& splitX(LinkList<T>* list2);
protected:
	Node<T>* headofList;
	int listSize;
};
template <class T>
LinkList<T>::LinkList()
{
	headofList = new Node<T>;
	headofList->head = headofList;
	headofList->tail = headofList;
	listSize = 0;
}
template <class T>
LinkList<T>::LinkList(const LinkList<T>& List)
{
	listSize = List.listSize;
	if (List.listSize == 0) {
		headofList = new Node<T>;
		headofList->head = headofList;
		headofList->tail = headofList;
		return;
	}
	Node<T>* oldHead = List.headofList;
	oldHead = oldHead->tail;
	headofList = new Node<T>;
	Node<T>* movingNode = headofList;
	while (oldHead != List.headofList) {
		movingNode->tail = new Node<T>(oldHead->data, movingNode,headofList);
		movingNode = movingNode->tail;
		oldHead = oldHead->tail;
	}
	headofList->head = movingNode;
	return;
}
template <class T>
LinkList<T>::~LinkList()
{
	while (headofList->head != headofList->tail && headofList->head != headofList) {
		Node<T>* temp = headofList->tail;
		temp->head = headofList->head;
		headofList->head->tail = temp;
		delete headofList;
		headofList = temp;
	}
	delete headofList;
	return;
}
template <class T>
T& LinkList<T>::get(int theIndex) const
{
	Node<T>* tempNode = headofList;
	for (int i = 0; i < theIndex ; i++)
		tempNode = tempNode->tail;
	return tempNode->data;
}
template <class T>
int LinkList<T>::indexOf(const T& theElement) const
{
	int index = 1;
	Node<T>* tempNode = headofList->tail;
	while (tempNode!=headofList&&tempNode->data != theElement) {
		index++;
		tempNode = tempNode->tail;
	}
	if (tempNode->data != theElement)
		return -1;
	return index;
}
template <class T>
void LinkList<T>::erase(int theIndex)
{
	if (theIndex < 1 || theIndex > listSize)
		return;
	Node<T>* deletedNode;
	Node<T>* afterNode;
	Node<T>* preNode = headofList;
	for (int i = 0; i < theIndex - 1; i++)
		preNode = preNode->tail;
	deletedNode = preNode->tail;
	afterNode = deletedNode->tail;
		
	preNode->tail = afterNode;
	afterNode->head = preNode;
	listSize--;
	deletedNode->head = NULL;              
	deletedNode->tail = NULL;
	delete deletedNode;
	return;
}
template <class T>
void LinkList<T>::insert(int theIndex, const T& theElement)
{
	if (theIndex < 0 || theIndex > listSize)
		return;
	else if (theIndex == 0) {
		Node<T>* targetNode = new Node<T>(theElement, headofList, headofList->tail);
		targetNode->tail->head = targetNode;
		headofList->tail = targetNode;
	}
	else {
		Node<T>* preNode = headofList;
		for (int i = 0; i < theIndex - 1; i++)
			preNode = preNode->tail;
		Node<T>* targetNode = new Node<T>(theElement, preNode, preNode->tail);
		targetNode->tail->head = targetNode;
		preNode->tail = targetNode;
	}
	listSize++;
	return;
}
template <class T>
void LinkList<T>::output(std::ostream& out) const
{

	out << "{";
	if ((headofList->head == headofList->tail) && (headofList->head == headofList))
		out << "}" << '\n';
	else {
		for (Node<T>* currentNode = headofList->tail; ; currentNode = currentNode->tail) {
			if (currentNode->tail != headofList)
				out << currentNode->data << ",";
			else {
				out << currentNode->data << "}" << '\n';
				return;
			}
		}
	}
}
template <class T>
void LinkList<T>::push_back(const T& theElement)
{
	if ((headofList->head == headofList->tail) && (headofList->head == headofList)) {
		Node<T>* targetNode = new Node<T>(theElement,headofList,headofList);
		headofList->head = headofList->tail = targetNode;
	}
	else {
		Node<T>* lastNode = headofList;
		while (lastNode->tail != headofList)
			lastNode = lastNode->tail;
		lastNode->tail = new Node<T>(theElement, lastNode,headofList);
		headofList->head = lastNode->tail;
	}
	listSize++;
	return;
}
template <class T>
bool LinkList<T>::isEmpty()
{
	if ((headofList -> head == headofList -> tail) &&(headofList->head == headofList))
		return true;
	return false;
}
template <class T>
std::ostream& operator<< (std::ostream& out, const LinkList<T>& list)
{
	list.output(out);
	return out;
}
template <class T>
LinkList<T>& LinkList<T>:: splitX(LinkList<T>* list2) {
	if (this->isEmpty()||listSize == 1)
		return* this;
	int count = 1;
	int size = this->getsize();
	list2->headofList->tail = headofList->tail->tail;
	Node<T>* currentNode1 = headofList->tail;
	Node<T>* currentNode2 = list2->headofList;
	while (count < size+1) {
		if (count % 2 == 1) {
			count++;
			currentNode1 = currentNode1->tail;
		}
		else {
			//list2.push_back(this->get((count + 3) / 2));
			currentNode2->tail = currentNode1;
			currentNode1->head->tail = currentNode1->tail;
			currentNode1->tail->head = currentNode1->head;
			currentNode1 = currentNode1->tail;
			currentNode2 = currentNode2->tail;
			//this->erase((count + 3) / 2);
			count++;
		}
		currentNode2->tail = list2->headofList;
	}
	currentNode2 = list2->headofList;
	for (int i = 0; i < size / 2; i++) {
		currentNode2->tail->head = currentNode2;
		currentNode2 = currentNode2->tail;
	}
	return* this;
}